//在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。 
//
// 
//
// 示例 1： 
//
// 输入：nums = [3,4,3,3]
//输出：4
// 
//
// 示例 2： 
//
// 输入：nums = [9,1,7,9,7,9,7]
//输出：1 
//
// 
//
// 限制： 
//
// 
// 1 <= nums.length <= 10000 
// 1 <= nums[i] < 2^31 
// 
//
// 
// Related Topics 位运算 数组 👍 271 👎 0

package com.cute.leetcode.editor.cn;
public class ShuZuZhongShuZiChuXianDeCiShuIiLcof {
    public static void main(String[] args) {
        int[] nums = {1,1,1,6};
        new ShuZuZhongShuZiChuXianDeCiShuIiLcof().new Solution().singleNumber(nums);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 只有一个数出现了一次
         * 剩下的数都出现了三次
         * tnnd，还跟我玩阴的是吧，那我也不演了，直接来吧！（又看题解，位运算还是真看不出来）
         * int类型的数据一共有32位，对所有的数字每一位的1进行统计
         * 出现三次的数字该位1的次数一定能被3整除
         * 统计完所有的次数之后，遍历，如果当前次数不能被3整除，那么只出现一次的数当前位一定为1
         */
        public int singleNumber(int[] nums) {
            int[] bitCount = new int[32];
            for (int num : nums){// 对num每一位的1进行计数，从最低位开始
                for (int i = 31; i >= 0 ; i--) {
                    bitCount[i] += num & 1;
                    num >>>= 1;
                }
            }
            int res = 0;
            for (int bit : bitCount){// 拼接最终结果，从最高位开始
                res <<= 1;
                res += bit % 3;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}